package 剑指Offer.中等;


import java.util.HashSet;
import java.util.Set;

/**
 * 
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 *
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author caihe
 * @date 2022/10/12 9:32
 */
public class _38字符串的排列 {

    static char[] chars;
    static Set<String> resList;
    public String[] permutation(String s) {
        if (s.length() == 0) {
            return new String[0];
        }
        chars = s.toCharArray();
        resList = new HashSet<>();
        dfs(0);
        return resList.toArray(new String[0]);
    }
    
    void dfs(int k) {
        if (k == chars.length) {
            System.out.println(new String(chars));
            resList.add(new String(chars));
        } else {
            Set<Character> set = new HashSet<>();
            for (int i = k; i < chars.length; i++) {
                char tmp = chars[i];
                if (set.contains(tmp)) {
                    continue;
                }
                set.add(tmp);
                chars[i] = chars[k];
                chars[k] = tmp;
                dfs(k + 1);
                tmp = chars[i];
                chars[i] = chars[k];
                chars[k] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        _38字符串的排列 a = new _38字符串的排列();
        a.permutation("abc");

    }
}
